Conventional content addressable memory (CAM) has been implemented primarily using static random access memory (SRAM) cells. SRAM-based CAMs have received widespread use due to the high access speed of SRAM memory cells and the static nature of the cells. Furthermore, SRAM cells can be manufactured using a pure-logic type fabrication process, which is commonly used for non-memory circuit blocks.
In addition to random access memory (RAM) functions, such as writing and reading data, CAMs are also capable of performing searches. Generally, stored data is retrieved and compared with target data for determining if the stored and target data match. If the stored and target data do match, a match result is indicated, otherwise a mismatch result is indicated. Thus, CAMs are particularly useful for fully associative memories such as look-up tables and memory-management units.
Many current applications utilize ternary CAMs, which are capable of storing three logic states. For example, the three logic states are logic ‘0’, logic ‘1’ and ‘don't care’. Therefore, such CAM cells require two memory cells to store the logic states, as well as a comparison circuit for comparing stored data with search data provided to the CAM.
However, various problems exist with semiconductor memories and, thus, affect CAMs as well. One such type of error, referred to as “soft errors”, are a well-known problem. The major cause of soft errors is alpha particle radiation, which can generate numerous electron hole pairs when it strikes a transistor diffusion area. These electron hole pairs can flip the state of data stored in a semiconductor memory cell. Clearly this is an undesirable occurrence. It is often important to detect that such an error has occurred and correct it if possible.
Error detection and correction has been attempted previously by using Hamming codes. Hamming codes typically require 5 extra bits per 32 bits or 7 extra bits per 64 bits, resulting in a data storage overhead of 15.6% or 10.9% respectively. Hamming codes in CAMs typically require 8 extra bits per 72 bits, for a data storage overhead of 11.1%. Evaluating the Hamming code also requires additional logic cycles and, thus, it can be time consuming to detect an error.
Alternately, it is possible to use parity bits. Generally, a parity bit is a bit that is appended to a word for representing the number of bits in the word that have a value ‘1’. In an example of odd parity, if the number of bits that are a ‘1’ is even, then the parity bit is ‘1’. If the number of bits that are ‘1’ is odd, then the parity bit is ‘0’. The concept of parity bits in general is well known in the art and need not be described in greater detail.
The concept of using horizontal and vertical parity in a semiconductor memory is described in U.S. Pat. Nos. 4,456,980 and 4,747,080 issued to Yamada et al. Generally, however, the method described by Yamada requires complex circuitry and many wide buses to implement. However the requirement for many wide buses renders this idea impractical as the area consumed to route so many signals makes the design cost prohibitive to manufacture.
In addition, reference may be made to the following patents and publications. U.S. Pat. No. 6,353,910 (Carnevale) discloses the storing ECC data within the array and exemplifies the complexity of non-parity based systems. U.S. Pat. No. 5,127,014 (Raynham) discloses the addition of ECC to a DRAM memory and the scrubbing of errors during a refresh cycle. The ECC data adds significant overhead. U.S. Pat. Nos. 4,456,980 and 4,747,080 (see above) introduce the XY parity concept in a semiconductor memory. However they require significant wide bussing and are not practical. U.S. Pat. No. 4,183,463 (Kemmetmueller) discloses a two-dimensional parity scheme. U.S. Pat. No. 6,125,466 (Close) discloses two-dimensional parity in a subset of the array. U.S. Pat. No. 5,134,616 (Barth) discloses a memory with hamming codes at the end of the wordline. It adds redundancy. U.S. Pat. Nos. 4,688,219 and 4,768,193 (Takemae) disclose another two-dimensional parity scheme with very complex bussing. Finally, in a paper by Pinaki Mazumder (Pinaki Mazumder, “An On-Chip ECC Circuit for Correcting Soft Errors in DRAM's with Trench Capacitors”, IEEE JSSC, Vol. 27, No. 11, November 1992), a horizontal, vertical and diagonal parity scheme is disclosed with all the parity bits stored on the same word line. However, this paper does not disclose true horizontal and vertical parity in space, as all parity bits are stored on the same wordline.
A need, therefore, exists for an improved circuit and method for error detection and correction in CAMs. Consequently, it is an object of the present invention to obviate or mitigate at least some of the above mentioned disadvantages.